package algocasts;

import java.util.Stack;

public class P17_MinStack {
    class MinStack_TwoStack {
        private Stack<Integer> stack;
        private Stack<Integer> min;

        public MinStack_TwoStack() {
            stack = new Stack<>();
            min = new Stack<>();
        }

        public void push(int x) {
            stack.push(x);
            if (min.isEmpty() || x <= min.peek())
                min.push(x);
        }

        public void pop() {
            if (stack.peek() == min()) min.pop();
            stack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int min() {
            return stack.peek();
        }
    }

    class MinStack_LinkedList {

        private class Node {
            int val;
            Node next;

            Node(int val, Node next) {
                this.val = val;
                this.next = next;
            }
        }

        private Node head;
        private int min;

        public MinStack_LinkedList() {
            head = null;
            min = Integer.MAX_VALUE;
        }

        public void push(int x) {
            if (x <= min) {
                head = new Node(min, head);
                min = x;
            }
            head = new Node(x, head);
        }

        public void pop() {
            if (head.val == min) {
                min = head.next.val;
                head = head.next.next;
            } else {
                head = head.next;
            }
        }

        public int top() {
            return head.val;
        }

        public int min() {
            return min;
        }
    }
}
